{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Fraction Addition and Subtraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fractionAddition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分数加减运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个表示分数加减运算的字符串&nbsp;<code>expression</code>&nbsp;，你需要返回一个字符串形式的计算结果。&nbsp;</p>\n",
    "\n",
    "<p>这个结果应该是不可约分的分数，即<a href=\"https://baike.baidu.com/item/%E6%9C%80%E7%AE%80%E5%88%86%E6%95%B0\" target=\"_blank\">最简分数</a>。&nbsp;如果最终结果是一个整数，例如&nbsp;<code>2</code>，你需要将它转换成分数形式，其分母为&nbsp;<code>1</code>。所以在上述例子中, <code>2</code>&nbsp;应该被转换为&nbsp;<code>2/1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;<code>expression</code>&nbsp;= \"-1/2+1/2\"\n",
    "<strong>输出:</strong> \"0/1\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>&nbsp;示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;<code>expression</code>&nbsp;= \"-1/2+1/2+1/3\"\n",
    "<strong>输出:</strong> \"1/3\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong>&nbsp;<code>expression</code>&nbsp;= \"1/3-1/2\"\n",
    "<strong>输出:</strong> \"-1/6\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>输入和输出字符串只包含&nbsp;<code>'0'</code> 到&nbsp;<code>'9'</code>&nbsp;的数字，以及&nbsp;<code>'/'</code>, <code>'+'</code> 和&nbsp;<code>'-'</code>。&nbsp;</li>\n",
    "\t<li>输入和输出分数格式均为&nbsp;<code>±分子/分母</code>。如果输入的第一个分数或者输出的分数是正数，则&nbsp;<code>'+'</code>&nbsp;会被省略掉。</li>\n",
    "\t<li>输入只包含合法的<strong>最简分数</strong>，每个分数的<strong>分子</strong>与<strong>分母</strong>的范围是&nbsp;&nbsp;[1,10]。&nbsp;如果分母是1，意味着这个分数实际上是一个整数。</li>\n",
    "\t<li>输入的分数个数范围是 [1,10]。</li>\n",
    "\t<li><strong>最终结果</strong>的分子与分母保证是 32 位整数范围内的有效整数。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fraction-addition-and-subtraction](https://leetcode.cn/problems/fraction-addition-and-subtraction/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fraction-addition-and-subtraction](https://leetcode.cn/problems/fraction-addition-and-subtraction/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"-1/2+1/2\"', '\"-1/2+1/2+1/3\"', '\"1/3-1/2\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        # 利用正则表达式\n",
    "        # eval(expression)将字符串转化成可以计算的表达式\n",
    "        a = eval(expression)\n",
    "        f = Fraction(str(eval(expression))).limit_denominator()    \n",
    "        return f'{f.numerator}/{f.denominator}'\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    expression = \"-1/2+1/2\"\n",
    "    sol = Solution()\n",
    "    print(sol.fractionAddition(expression))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "ptn = re.compile(r'[+-]?\\d+/\\d+')\n",
    "class Solution:\n",
    "    def fractionAddition(self, expr: str) -> str:\n",
    "        res = sum(Fraction(f) for f in ptn.findall(expr))\n",
    "        return f'{res.numerator}/{res.denominator}'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        denominator, numerator = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            denominator1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():  # 遍历到数字\n",
    "                denominator1 = denominator1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            denominator1 = sign * denominator1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            numerator1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                numerator1 = numerator1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            denominator = denominator * numerator1 + denominator1 * numerator\n",
    "            numerator *= numerator1\n",
    "        if denominator == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(denominator), numerator)\n",
    "        return f\"{denominator // g}/{numerator // g}\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        expression=expression.replace(\"-\",\"+-\").strip(\"+\").split(\"+\")\n",
    "        \n",
    "        \n",
    "        def get_maxbei(a,b):\n",
    "            return a*b//gcd(a,b)\n",
    "        \n",
    "        def plus(num1:str,num2:str):\n",
    "            fz1,fm1=map(int,num1.split(\"/\"))\n",
    "            fz2,fm2=map(int,num2.split(\"/\"))\n",
    "            maxb=get_maxbei(fm1,fm2)\n",
    "            fz=fz1*(maxb//fm1)+fz2*(maxb//fm2)\n",
    "            g=gcd(fz,maxb)\n",
    "            \n",
    "            return \"/\".join([str(fz//g),str(maxb//g)])\n",
    "        ans=\"0/1\"\n",
    "        for x in expression:\n",
    "            ans=plus(ans,x)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "ptn = re.compile(r'[+-]?\\d+/\\d+')\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def fractionAddition(self, expr: str) -> str:\n",
    "\n",
    "        res = sum(Fraction(f) for f in ptn.findall(expr))\n",
    "\n",
    "        return f'{res.numerator}/{res.denominator}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def gcd(a, b):\n",
    "            if a % b == 0:\n",
    "                return b\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        op = \"\"\n",
    "        nums = []\n",
    "        s = expression\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i].isdigit():\n",
    "                num = 0\n",
    "                while i < n and s[i].isdigit():\n",
    "                    num = num * 10 + int(s[i])\n",
    "                    i += 1\n",
    "                if op == \"-\":\n",
    "                    num = -num\n",
    "                nums.append(num)\n",
    "                if op == \"/\":\n",
    "                    b = nums.pop()\n",
    "                    a = nums.pop()\n",
    "                    nums.append((a, b))\n",
    "            else:\n",
    "                op = s[i]\n",
    "                i += 1\n",
    "        \n",
    "        while len(nums) > 1:\n",
    "            a, b = nums.pop()\n",
    "            c, d = nums.pop()\n",
    "            x, y = a * d + b * c, b * d\n",
    "            g = gcd(abs(x), abs(y))\n",
    "            x, y = x // g, y // g\n",
    "            nums.append((x, y))\n",
    "        \n",
    "        a, b = nums[0]\n",
    "        return f\"{a}/{b}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, n = 0, len(expression)\n",
    "        a, b = 0, 1\n",
    "        while x < n:\n",
    "            a1, b1, sign = 0, 0, 1\n",
    "            if expression[x] == '-' or expression[x] == '+':\n",
    "                if expression[x] == '-':\n",
    "                    sign = -1\n",
    "                x += 1\n",
    "            while x < n and expression[x].isdigit():\n",
    "                a1 = 10 * a1 + int(expression[x])\n",
    "                x += 1\n",
    "            a1 *= sign \n",
    "            x += 1\n",
    "            while x < n and expression[x].isdigit():\n",
    "                b1 = b1 * 10 + int(expression[x])\n",
    "                x += 1\n",
    "            a = a * b1 + a1 * b\n",
    "            b *= b1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = math.gcd(abs(a), b)\n",
    "        return \"{}/{}\".format(a // g, b // g)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        # 可以不单写成函数，放在同一个循环里更简洁\n",
    "        def read_number(i: int):\n",
    "            sign, numerator, denominator = -1 if expression[i] == '-' else 1, 0, 0\n",
    "            if expression[i] in \"+-\":\n",
    "                i += 1\n",
    "            while i < len(expression) and expression[i] != '/':\n",
    "                numerator = 10 * numerator + int(expression[i])\n",
    "                i += 1\n",
    "            i += 1\n",
    "            while i < len(expression) and expression[i] not in \"+-\":\n",
    "                denominator = 10 * denominator + int(expression[i])\n",
    "                i += 1\n",
    "            return sign * numerator, denominator if denominator else 1, i\n",
    "        \n",
    "        idx = numer = 0\n",
    "        denom = 1\n",
    "        while idx < len(expression):\n",
    "            num, den, idx = read_number(idx)\n",
    "            lm = lcm(denom, den)\n",
    "            numer, denom = numer * lm // denom + num * lm // den, lm\n",
    "        g = gcd(abs(numer), denom)\n",
    "        return f\"{numer // g}/{denom // g}\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\"\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] in ('+', '-'):\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 +int(expression[i])\n",
    "                i += 1\n",
    "            x1 = x1 * sign\n",
    "            \n",
    "            i += 1\n",
    "\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 +int(expression[i])\n",
    "                i += 1\n",
    "            \n",
    "            x = x*y1 + x1*y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return '0/1'\n",
    "        g = math.gcd(x, y)\n",
    "        return f'{x//g}/{y//g}'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "ptn = re.compile(r'[+-]?\\d+/\\d+')\n",
    "class Solution:\n",
    "    def fractionAddition(self, expr: str) -> str:\n",
    "        res = sum(Fraction(f) for f in ptn.findall(expr))\n",
    "        return f'{res.numerator}/{res.denominator}'\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        r = re.compile(\"(\\-|\\+?)(10|[0-9])/(10|[0-9])\")\n",
    "        res = 0\n",
    "        for i in r.findall(expression):\n",
    "            k = int(i[1]) * (2520//int(i[2]))\n",
    "            if i[0] == \"-\":\n",
    "                res -= k\n",
    "            else:\n",
    "                res +=k\n",
    "        div = math.gcd(res, 2520)\n",
    "        return \"%d/%d\" % (res // div, 2520//div)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        def lcm(denominators):\n",
    "            return reduce(lambda a,b: a*b // gcd(a,b), denominators)\n",
    "        numerator, denominator = [], []\n",
    "        positive = True\n",
    "        numer = True\n",
    "        i = 0\n",
    "        n = len(expression)\n",
    "        # for i, c in enumerate(expression):\n",
    "        while i < len(expression):\n",
    "            c = expression[i]\n",
    "            if c == '-':\n",
    "                positive = False\n",
    "            elif c == '+':\n",
    "                positive = True\n",
    "            elif numer == True and c != '/':\n",
    "                if positive == True:\n",
    "                    if i + 1 < n and expression[i + 1] != '/':\n",
    "                        numerator.append(int(expression[i:i+2]))\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        numerator.append(int(c))\n",
    "                else:\n",
    "                    if i + 1 < n and expression[i + 1] != '/':\n",
    "                        numerator.append(-int(expression[i:i+2]))\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        numerator.append(-int(c))\n",
    "                numer = False\n",
    "            elif numer == False and c!= '/':\n",
    "                # denominator.append(int(c))\n",
    "                if i + 1 < n and expression[i + 1] not in '+-':\n",
    "                        denominator.append(int(expression[i:i+2]))\n",
    "                        i += 1\n",
    "                else:\n",
    "                    denominator.append(int(c))\n",
    "                numer = True\n",
    "            i += 1\n",
    "        common_denominator = lcm(tuple(denominator))\n",
    "        for i, n in enumerate(numerator):\n",
    "            numerator[i] = int(common_denominator / denominator[i] * n)\n",
    "        res_numerator = sum(numerator)\n",
    "        common_devisor = math.gcd(common_denominator, res_numerator)\n",
    "        d =  common_denominator / common_devisor\n",
    "        n = res_numerator / common_devisor\n",
    "        # if n < 0:\n",
    "        #     ans = '-'\n",
    "        # else:\n",
    "        #     ans = ''\n",
    "        ans = ''\n",
    "        ans = ans + str(int(n))\n",
    "        ans = ans + '/'\n",
    "        ans = ans + str(int(d))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        f=Fraction(eval(expression)).limit_denominator()\n",
    "        ans=str(f)\n",
    "        if f%1==0:\n",
    "            ans+='/1'\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i = 0\n",
    "        while i < len(expression):\n",
    "            x1, y1 = 0, 0\n",
    "            sign = 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            #读取分子\n",
    "            while i < len(expression) and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 *= sign\n",
    "            i += 1 #跳过/\n",
    "            #读取分母\n",
    "            while i < len(expression) and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x = x * y1 + x1 * y\n",
    "            y = y * y1\n",
    "        #求x,y最大公因数\n",
    "        g = gcd(abs(x), y)\n",
    "        if x == 0:\n",
    "            return '0/1'\n",
    "        return f'{x//g}/{y//g}'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "ptn = re.compile(r'[+-]?\\d+/\\d+')\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        res = sum(Fraction(f) for f in ptn.findall(expression))\n",
    "        return f'{res.numerator}/{res.denominator}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        idx = 0\n",
    "        l = len(expression)\n",
    "        denominators = []\n",
    "        minators = []\n",
    "        exp = expression.split('/')\n",
    "        minators.append(int(exp[0]))\n",
    "        for i in exp[1:len(exp)-1]:\n",
    "            if '+' in i:\n",
    "                a, b = i.split('+')\n",
    "                minators.append(int(b))\n",
    "                denominators.append(int(a))\n",
    "            else:\n",
    "                a, b = i.split('-')\n",
    "                minators.append(-int(b))\n",
    "                denominators.append(int(a))\n",
    "        denominators.append(int(exp[-1]))\n",
    "        plus = 1\n",
    "        for i in set(denominators):\n",
    "            plus *= i\n",
    "        minator = sum(minators[i] * plus // denominators[i] for i in range(len(minators)))\n",
    "        def pcb(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            else:\n",
    "                return pcb(b, a%b)\n",
    "        x = pcb(abs(minator),plus)\n",
    "        return str(minator//x) + '/' + str(plus//x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def fractionAddition(self, expression):\n",
    "        \"\"\"\n",
    "        :type expression: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        x,y=0,1\n",
    "        i,n=0,len(expression)\n",
    "        while i<n:\n",
    "            #读取分子\n",
    "            x1,sign=0,1\n",
    "            #判断正负\n",
    "            if expression[i]=='-'or expression[i]=='+':\n",
    "                if expression[i]=='-':\n",
    "                    sign=-1\n",
    "                i+=1\n",
    "            #判断是不是数字的函数\n",
    "            while i<n and expression[i].isdigit():\n",
    "                x1=x1*10 + int(expression[i])\n",
    "                i+=1\n",
    "            x1=sign*x1\n",
    "            i+=1\n",
    "\n",
    "            y1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1= y1*10+int(expression[i])\n",
    "                i+=1\n",
    "\n",
    "            x=x*y1+x1*y\n",
    "            y*=y1\n",
    "        if x==0:\n",
    "            return \"0/1\"\n",
    "        #计算x和y的最大公约数，然后用x和y分别约分\n",
    "        g=math.gcd(abs(x),y)\n",
    "        x=int(x/g)\n",
    "        y=int(y/g)\n",
    "        return str(x)+\"/\"+str(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        def find_max(nums1, nums2):\n",
    "            index = 1\n",
    "            nums1_list = []\n",
    "            nums2_list = []\n",
    "            while True:\n",
    "                nums1_list.append(nums1 * index)\n",
    "                nums2_list.append(nums2 * index)\n",
    "                if set(nums1_list) & set(nums2_list):\n",
    "                    return list(set(nums1_list) & set(nums2_list))[0]\n",
    "                else:\n",
    "                    index += 1\n",
    "\n",
    "        def find_min(nums1, nums2):\n",
    "            flag = 0\n",
    "            if nums1 < 0:\n",
    "                nums1 = -nums1\n",
    "                flag = 1\n",
    "            for i in range(min(nums1, nums2), 1, -1):\n",
    "                while nums1//i == nums1/i and nums2//i == nums2/i:\n",
    "                    nums1 = nums1//i\n",
    "                    nums2 = nums2//i\n",
    "            if nums1 == 0:\n",
    "                return '0/1'\n",
    "            return str(-nums1) + '/' + str(nums2) if flag else str(nums1) + '/' + str(nums2)\n",
    "\n",
    "        cal_list = []\n",
    "        flag = 0\n",
    "        for i in expression[1:]:\n",
    "            if i in ['-', '+']:\n",
    "                cal_list.append(i)\n",
    "        expression = expression.replace('+', '-')\n",
    "        if expression[0] == '-':\n",
    "            expression = expression[1:]\n",
    "            flag = 1\n",
    "        nums = expression.split('-')\n",
    "        n = len(nums)\n",
    "        index = 0\n",
    "        while index <= n-2:\n",
    "            fenzi_1, fenmu_1 = map(int, list(nums[index].split('/')))\n",
    "            fenzi_2, fenmu_2 = map(int, list(nums[index+1].split('/')))\n",
    "            if index == 0 and flag:\n",
    "                fenzi_1 = -fenzi_1\n",
    "            com_max = lcm(fenmu_1, fenmu_2)\n",
    "            if cal_list[index] == '+':\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 + com_max/fenmu_2*fenzi_2)\n",
    "            else:\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 - com_max/fenmu_2*fenzi_2)\n",
    "            fenmu_2 = com_max\n",
    "            nums[index+1] = str(fenzi_2) + '/' + str(fenmu_2)\n",
    "            index += 1\n",
    "        fenzi, fenmu= map(int, list(nums[-1].split('/')))\n",
    "        if n == 1 and flag:\n",
    "            fenzi = -fenzi\n",
    "        return find_min(fenzi, fenmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        j=[]\n",
    "        start=0\n",
    "        for i in range (1,len(expression)):\n",
    "            if expression[i]==\"+\"or expression[i]==\"-\":\n",
    "                j.append(expression[start:i])\n",
    "                start=i\n",
    "        j.append(expression[start:])\n",
    "        down=1\n",
    "        up=0\n",
    "        for x in j:\n",
    "            son,mom=x.split(\"/\")\n",
    "            up=up*int(mom)+int(son)*down\n",
    "            down=down*int(mom)\n",
    "        if up==0:\n",
    "            return \"0/1\"\n",
    "        jk=math.gcd(up,down)\n",
    "        up=up//jk\n",
    "        down=down//jk\n",
    "        return  str(up)+\"/\"+str(down)  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x,y=0,1\n",
    "        i,n=0,len(expression)\n",
    "        while i<n:\n",
    "            x1,sign=0,1\n",
    "            if expression[i]=='-' or expression[i]=='+':\n",
    "                if expression[i]=='-':\n",
    "                    sign=-1\n",
    "                i+=1\n",
    "            \n",
    "            while i<n and expression[i].isdigit():\n",
    "                x1=x1*10+int(expression[i])\n",
    "                i+=1\n",
    "            x1=sign*x1\n",
    "            i+=1\n",
    "\n",
    "            y1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1=y1*10+int(expression[i])\n",
    "                i+=1\n",
    "            x=x*y1+x1*y\n",
    "            y*=y1\n",
    "\n",
    "        if x==0:\n",
    "            return \"0/1\"\n",
    "        \n",
    "        g=gcd(abs(x),y)\n",
    "        return f\"{x//g}/{y//g}\"\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        res = 0\n",
    "        if expression[0] == '-':\n",
    "            start = 1\n",
    "            op = -1\n",
    "        else:\n",
    "            start = 0\n",
    "            op = 1\n",
    "        for i in range(start, len(expression)):\n",
    "            if expression[i] == '+':\n",
    "                res += op * Fraction(expression[start:i])\n",
    "                op = 1\n",
    "                start = i + 1\n",
    "            elif expression[i] == '-':\n",
    "                res += op * Fraction(expression[start:i])\n",
    "                op = -1\n",
    "                start = i + 1\n",
    "        res += op * Fraction(expression[start:])\n",
    "        \n",
    "        return f\"{res.numerator}/{res.denominator}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def lt592(s):\n",
    "            is_numerator=1\n",
    "            num_stack=[]\n",
    "            numerators,denominators=[],[]\n",
    "\n",
    "            for ch in s:\n",
    "                if ch=='+' and num_stack:\n",
    "                    if is_numerator:\n",
    "                        numerators.append(int(''.join(num_stack)))\n",
    "                        denominators.append(1)\n",
    "                    else:\n",
    "                        denominators.append(int(''.join(num_stack)))\n",
    "                        is_numerator=1\n",
    "                    num_stack = []\n",
    "                elif ch=='-':\n",
    "                    if num_stack:\n",
    "                        if is_numerator:\n",
    "                            numerators.append(int(''.join(num_stack)))\n",
    "                            denominators.append(1)\n",
    "                        else:\n",
    "                            denominators.append(int(''.join(num_stack)))\n",
    "                            is_numerator=1\n",
    "                    num_stack=['-']\n",
    "                elif ch=='/':\n",
    "                    if num_stack:\n",
    "                        numerators.append(int(''.join(num_stack)))\n",
    "                        num_stack=[]\n",
    "                    is_numerator=0\n",
    "                else:num_stack.append(ch)\n",
    "            if is_numerator:\n",
    "                numerators.append(int(''.join(num_stack)))\n",
    "                denominators.append(1)\n",
    "            else:denominators.append(int(''.join(num_stack)))\n",
    "\n",
    "            if not denominators:return sum(numerators)\n",
    "\n",
    "            lcm=math.lcm(*denominators)\n",
    "            for i in range(len(denominators)):\n",
    "                numerators[i]*=(lcm//denominators[i])\n",
    "            nu=sum(numerators)\n",
    "            gcd=math.gcd(nu,lcm)\n",
    "            nu//=gcd\n",
    "            lcm//=gcd\n",
    "            # if lcm == 1: return str(nu)\n",
    "            return str(nu)+'/'+str(lcm)\n",
    "        return lt592(expression)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        def find_max(nums1, nums2):\n",
    "            index = 1\n",
    "            nums1_list = []\n",
    "            nums2_list = []\n",
    "            while True:\n",
    "                nums1_list.append(nums1 * index)\n",
    "                nums2_list.append(nums2 * index)\n",
    "                if set(nums1_list) & set(nums2_list):\n",
    "                    return list(set(nums1_list) & set(nums2_list))[0]\n",
    "                else:\n",
    "                    index += 1\n",
    "\n",
    "        def find_min(nums1, nums2):\n",
    "            flag = 0\n",
    "            if nums1 < 0:\n",
    "                nums1 = -nums1\n",
    "                flag = 1\n",
    "            for i in range(min(nums1, nums2), 1, -1):\n",
    "                while nums1//i == nums1/i and nums2//i == nums2/i:\n",
    "                    nums1 = nums1//i\n",
    "                    nums2 = nums2//i\n",
    "            if nums1 == 0:\n",
    "                return '0/1'\n",
    "            return str(-nums1) + '/' + str(nums2) if flag else str(nums1) + '/' + str(nums2)\n",
    "\n",
    "        cal_list = []\n",
    "        flag = 0\n",
    "        for i in expression[1:]:\n",
    "            if i in ['-', '+']:\n",
    "                cal_list.append(i)\n",
    "        expression = expression.replace('+', '-')\n",
    "        if expression[0] == '-':\n",
    "            expression = expression[1:]\n",
    "            flag = 1\n",
    "        nums = expression.split('-')\n",
    "        n = len(nums)\n",
    "        index = 0\n",
    "        while index <= n-2:\n",
    "            fenzi_1, fenmu_1 = map(int, list(nums[index].split('/')))\n",
    "            fenzi_2, fenmu_2 = map(int, list(nums[index+1].split('/')))\n",
    "            if index == 0 and flag:\n",
    "                fenzi_1 = -fenzi_1\n",
    "            com_max = lcm(fenmu_1, fenmu_2)\n",
    "            if cal_list[index] == '+':\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 + com_max/fenmu_2*fenzi_2)\n",
    "            else:\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 - com_max/fenmu_2*fenzi_2)\n",
    "            fenmu_2 = com_max\n",
    "            nums[index+1] = str(fenzi_2) + '/' + str(fenmu_2)\n",
    "            index += 1\n",
    "        fenzi, fenmu= map(int, list(nums[-1].split('/')))\n",
    "        if n == 1 and flag:\n",
    "            fenzi = -fenzi\n",
    "        return find_min(fenzi, fenmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        def find_max(nums1, nums2):\n",
    "            index = 1\n",
    "            nums1_list = []\n",
    "            nums2_list = []\n",
    "            while True:\n",
    "                nums1_list.append(nums1 * index)\n",
    "                nums2_list.append(nums2 * index)\n",
    "                if set(nums1_list) & set(nums2_list):\n",
    "                    return list(set(nums1_list) & set(nums2_list))[0]\n",
    "                else:\n",
    "                    index += 1\n",
    "\n",
    "        def find_min(nums1, nums2):\n",
    "            flag = 0\n",
    "            if nums1 < 0:\n",
    "                nums1 = -nums1\n",
    "                flag = 1\n",
    "            for i in range(min(nums1, nums2), 1, -1):\n",
    "                while nums1//i == nums1/i and nums2//i == nums2/i:\n",
    "                    nums1 = nums1//i\n",
    "                    nums2 = nums2//i\n",
    "            if nums1 == 0:\n",
    "                return '0/1'\n",
    "            return str(-nums1) + '/' + str(nums2) if flag else str(nums1) + '/' + str(nums2)\n",
    "\n",
    "        cal_list = []\n",
    "        flag = 0\n",
    "        for i in expression[1:]:\n",
    "            if i in ['-', '+']:\n",
    "                cal_list.append(i)\n",
    "        expression = expression.replace('+', '-')\n",
    "        if expression[0] == '-':\n",
    "            expression = expression[1:]\n",
    "            flag = 1\n",
    "        nums = expression.split('-')\n",
    "        n = len(nums)\n",
    "        index = 0\n",
    "        while index <= n-2:\n",
    "            fenzi_1, fenmu_1 = map(int, list(nums[index].split('/')))\n",
    "            fenzi_2, fenmu_2 = map(int, list(nums[index+1].split('/')))\n",
    "            if index == 0 and flag:\n",
    "                fenzi_1 = -fenzi_1\n",
    "            com_max = lcm(fenmu_1, fenmu_2)\n",
    "            if cal_list[index] == '+':\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 + com_max/fenmu_2*fenzi_2)\n",
    "            else:\n",
    "                fenzi_2 = int(com_max/fenmu_1*fenzi_1 - com_max/fenmu_2*fenzi_2)\n",
    "            fenmu_2 = com_max\n",
    "            nums[index+1] = str(fenzi_2) + '/' + str(fenmu_2)\n",
    "            index += 1\n",
    "        fenzi, fenmu= map(int, list(nums[-1].split('/')))\n",
    "        if n == 1 and flag:\n",
    "            fenzi = -fenzi\n",
    "        return find_min(fenzi, fenmu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def find_start_end(s, pivot):\n",
    "                fi, fj = pivot-1, pivot+1\n",
    "                while fi >= 0 and (expression[fi].isdigit()):\n",
    "                    fi -= 1\n",
    "                if expression[fi] == '-':\n",
    "                    fi -= 1\n",
    "                \n",
    "                while fj < len(expression) and expression[fj].isdigit():\n",
    "                    fj += 1\n",
    "                return fi, fj\n",
    "\n",
    "        def do_sum(a, b):\n",
    "            a_items = a.split('/')\n",
    "            a_s, a_e = int(a_items[0]), int(a_items[1])\n",
    "            b_items = b.split('/')\n",
    "            b_s, b_e = int(b_items[0]), int(b_items[1])\n",
    "\n",
    "            min_e = a_e * b_e\n",
    "            a_m = min_e // a_e\n",
    "            a_s = a_s * a_m\n",
    "            b_m = min_e // b_e\n",
    "            b_s = b_s * b_m\n",
    "            min_s = a_s + b_s\n",
    "        \n",
    "            import math\n",
    "            gcd = math.gcd(abs(min_s), abs(min_e))\n",
    "            min_s = min_s // gcd\n",
    "            min_e = min_e // gcd\n",
    "            \n",
    "            ret = str(min_s) + '/' + str(min_e)\n",
    "            return ret\n",
    "\n",
    "        while expression.count('/') > 1:\n",
    "            f_index = expression.find('/')\n",
    "            s_index = expression.find('/', f_index + 1)\n",
    "            fi, fj = find_start_end(expression, f_index)\n",
    "            si, sj = find_start_end(expression, s_index)\n",
    "            a, b = expression[fi + 1: fj], expression[si + 1: sj]\n",
    "            tmp_ret = do_sum(a, b)\n",
    "            expression = tmp_ret + expression[sj:]\n",
    "\n",
    "        return expression            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        expression=expression.replace(\"-\",\"+-\").strip(\"+\").split(\"+\")\n",
    "        \n",
    "        \n",
    "        def get_maxbei(a,b):\n",
    "            return a*b//gcd(a,b)\n",
    "        \n",
    "        def plus(num1:str,num2:str):\n",
    "            fz1,fm1=map(int,num1.split(\"/\"))\n",
    "            fz2,fm2=map(int,num2.split(\"/\"))\n",
    "            maxb=get_maxbei(fm1,fm2)\n",
    "            fz=fz1*(maxb//fm1)+fz2*(maxb//fm2)\n",
    "            g=gcd(fz,maxb)\n",
    "            \n",
    "            return \"/\".join([str(fz//g),str(maxb//g)])\n",
    "        ans=\"0/1\"\n",
    "        for x in expression:\n",
    "            ans=plus(ans,x)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        expression=expression.replace(\"-\",\"+-\").strip(\"+\").split(\"+\")\n",
    "        \n",
    "        \n",
    "        def get_maxbei(a,b):\n",
    "            return a*b//gcd(a,b)\n",
    "        \n",
    "        def plus(num1:str,num2:str):\n",
    "            fz1,fm1=map(int,num1.split(\"/\"))\n",
    "            fz2,fm2=map(int,num2.split(\"/\"))\n",
    "            maxb=get_maxbei(fm1,fm2)\n",
    "            fz=fz1*(maxb//fm1)+fz2*(maxb//fm2)\n",
    "            #g=gcd(fz,maxb)\n",
    "            \n",
    "            return \"/\".join([str(fz),str(maxb)])\n",
    "        ans=\"0/1\"\n",
    "        for x in expression:\n",
    "            ans=plus(ans,x)\n",
    "        \n",
    "        z,m=map(int,ans.split(\"/\"))\n",
    "        g=gcd(z,m)\n",
    "        \n",
    "        return \"/\".join([str(z//g),str(m//g)]) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1  # 跳过除号\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 解决问题的要点：1、要将正负号单独处理；2、多位数的时候如何处理，遍历，计算；3、python语言不要硬遍历\n",
    "\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        if expression[0] == '-':\n",
    "            st = 1\n",
    "            sgn = -1\n",
    "        else:\n",
    "            st = 0\n",
    "            sgn = 1\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(st,len(expression)):\n",
    "            if expression[i] == '+':\n",
    "                res += sgn * Fraction(expression[st:i])\n",
    "                st = i+1\n",
    "                sgn = 1\n",
    "            elif expression[i] == '-':\n",
    "                res += sgn * Fraction(expression[st:i])\n",
    "                st = i+1\n",
    "                sgn = -1\n",
    "        res += sgn * Fraction(expression[st:])\n",
    "        \n",
    "\n",
    "        return f\"{res.numerator}/{res.denominator}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def gcd(m,n):\n",
    "            if n == 0:\n",
    "                return m\n",
    "            else:\n",
    "                return gcd(n, m%n)\n",
    "        \n",
    "        flag = 1*2*3*4*5*6*7*8*9*10\n",
    "        if expression[0] != '+' and expression[0] != '-':\n",
    "            expression = '+' + expression\n",
    "        \n",
    "        state = ''\n",
    "        for letter in expression:\n",
    "            if letter == '+' or letter == '-':\n",
    "                state += '&' + letter\n",
    "            else:\n",
    "                state += letter\n",
    "\n",
    "        state = state.split('&')[1:]\n",
    "        s = 0\n",
    "        #print(state)\n",
    "        for x in state:\n",
    "            #print(x)\n",
    "            t = x[1:].split('/')\n",
    "            #print(t)\n",
    "            if x[0] == '+':\n",
    "                s += int(t[0]) * (flag // int(t[1]))\n",
    "            else:\n",
    "                s -= int(t[0]) * (flag // int(t[1]))\n",
    "        \n",
    "        k = gcd(s,flag)\n",
    "        s = s // k\n",
    "        flag = flag // k\n",
    "        \n",
    "        res = str(s) + '/' + str(flag)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            x1, y1, sign = 0, 0, 1\n",
    "            #读取符号\n",
    "            if expression[i] == '+' or expression[i] == '-':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            #读取分子\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = x1 * sign\n",
    "            #跳过\\\n",
    "            i += 1\n",
    "            #读取分母\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x = x * y1 + x1 * y\n",
    "            y = y * y1\n",
    "        g = gcd(abs(x), y)\n",
    "        if x == 0:\n",
    "            return '0/1'\n",
    "        return f'{x//g}/{y//g}'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        res=Fraction(str(eval(expression))).limit_denominator()\n",
    "        return f'{res.numerator}/{res.denominator}'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '+' or expression[i] == '-':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            y1 = 0\n",
    "            while i <n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 +int(expression[i])\n",
    "                i += 1\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return '0/1'\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\"\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "ptn = re.compile(r'[+-]?\\d+/\\d+')\n",
    "class Solution:\n",
    "    def fractionAddition(self, expr: str) -> str:\n",
    "        res = sum(Fraction(f) for f in ptn.findall(expr))\n",
    "        return f'{res.numerator}/{res.denominator}'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            y1 = 0\n",
    "            while i< n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + y * x1\n",
    "            y = y * y1\n",
    "        if x==0:\n",
    "            return '0/1'\n",
    "        g= math.gcd(x, y)\n",
    "        return f'{x//g}/{y//g}'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            sign = 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            x1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                x1=x1*10+int(expression[i])\n",
    "                i=i+1\n",
    "            x1=sign*x1\n",
    "            i=i+1\n",
    "            y1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1=y1*10+int(expression[i])\n",
    "                i=i+1\n",
    "            x=x*y1+x1*y\n",
    "            y=y*y1\n",
    "        if x==0:\n",
    "            return \"0/1\"\n",
    "        g=gcd(abs(x),y)\n",
    "        x=x//g\n",
    "        y=y//g\n",
    "        return str(x)+\"/\"+str(y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def fc1(string):\n",
    "    if string[0] not in ['-','+']:\n",
    "        return '+'+string\n",
    "    else:\n",
    "        return string\n",
    "\n",
    "def fc2(string):\n",
    "    lst2 = []\n",
    "    if string[0] not in ['-','+']:\n",
    "        string = '+'+string\n",
    "    for s in string:\n",
    "        if s in ['-','+']:\n",
    "            lst2.append(s)\n",
    "    string = string.replace('-','_').replace('+','_')\n",
    "    return string.split('_')[1:],lst2\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        fz = 0\n",
    "        fm = 2520\n",
    "        string = fc1(expression)\n",
    "        lst,lst1 = fc2(string)\n",
    "        n = len(lst)\n",
    "        # print('n',n)\n",
    "        for i in range(n):\n",
    "            s = lst[i]\n",
    "            # print('s',s)\n",
    "            fm1 = int(s.split('/')[1])\n",
    "            fz1 = int(s.split('/')[0])\n",
    "            fh = lst1[i]\n",
    "            bs = fm//fm1\n",
    "            if fh=='+':\n",
    "                fz+=fz1*bs\n",
    "            else:\n",
    "                fz-=fz1*bs\n",
    "        # print('fz,fm',fz,fm)\n",
    "        for i in [2,3,5,7]:\n",
    "            while ((not fz%i) and (not fm%i)):\n",
    "                fz = fz//i\n",
    "                fm = fm//i\n",
    "        return '{}/{}'.format(fz,fm)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fractionAddition(self, expression: str) -> str:\r\n",
    "        from re import findall\r\n",
    "        from functools import reduce\r\n",
    "        from math import gcd\r\n",
    "\r\n",
    "        def calculate(m, n):\r\n",
    "            divide1, divisor1 = map(int, m.split('/'))\r\n",
    "            divide2, divisor2 = map(int, n.split('/'))\r\n",
    "            lcm = divisor1 * divisor2 // gcd(divisor1, divisor2)  # 最小公倍数\r\n",
    "            divide = divide1 * (lcm // divisor1) + divide2 * (lcm // divisor2)\r\n",
    "            _gcd = gcd(divide, lcm)  # 用于约分的最大公因数\r\n",
    "            return f'{divide //_gcd}/{lcm // _gcd}'\r\n",
    "\r\n",
    "        return reduce(calculate, findall('[+-]?\\d+/\\d+', expression))\r\n",
    "\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i<n and expression[i].isdigit():\n",
    "                x1=x1*10+int(expression[i])\n",
    "                i=i+1\n",
    "            x1=sign*x1\n",
    "            i=i+1\n",
    "            y1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1=y1*10+int(expression[i])\n",
    "                i=i+1\n",
    "            x=x*y1+x1*y\n",
    "            y=y*y1\n",
    "        if x==0:\n",
    "            return \"0/1\"\n",
    "        g=gcd(abs(x),y)\n",
    "        x=x//g\n",
    "        y=y//g\n",
    "        return str(x)+\"/\"+str(y)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        pre = 0\n",
    "        n = len(expression)\n",
    "        x = 0  # 分子\n",
    "        y = 1  # 分母\n",
    "        for i in range(n):\n",
    "            if expression[i] == \"+\" or (expression[i] == \"-\" and i != 0):\n",
    "                [cur_x, cur_y] = [int(_) for _ in expression[pre: i].split(\"/\")]\n",
    "                x = x * cur_y + cur_x * y\n",
    "                y *= cur_y\n",
    "                pre = i\n",
    "        [cur_x, cur_y] = [int(_) for _ in expression[pre:].split(\"/\")]\n",
    "        x = x * cur_y + cur_x * y\n",
    "        y *= cur_y\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "\n",
    "        def gcd(a, b):\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "\n",
    "        t = gcd(x, y)\n",
    "        x //= t\n",
    "        y //= t\n",
    "        return f\"{x}/{y}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x = 0\n",
    "        y = 1 \n",
    "        sign = 1 \n",
    "        n = len(expression)\n",
    "        def add(x1,y1, x2, y2):\n",
    "            a = x1 * y2 + x2 * y1 \n",
    "            b = y1 * y2 \n",
    "            g = math.gcd(a, b) \n",
    "            return a // g, b // g \n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if expression[i] == '+':\n",
    "                i+=1\n",
    "                continue \n",
    "            elif expression[i] == '-':\n",
    "                i+=1\n",
    "                sign = -1 * sign \n",
    "            else:\n",
    "                nx, ny = 0, 0 \n",
    "                while i < n and expression[i] != '/':\n",
    "                    nx = nx * 10 + int(expression[i]) \n",
    "                    i+=1 \n",
    "                nx *= sign \n",
    "                sign = 1\n",
    "                i+=1 \n",
    "                while i < n and expression[i].isdigit():\n",
    "                    ny = ny * 10 + int(expression[i])\n",
    "                    i+=1\n",
    "                x, y = add(x, y, nx, ny) \n",
    "        return '{}/{}'.format(x, y) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_gcd(self, x, y):\n",
    "        if y == 0:\n",
    "            return 0\n",
    "        if x < y:\n",
    "            x, y = y, x\n",
    "        r = x % y\n",
    "        while r:\n",
    "            x = y\n",
    "            y = r \n",
    "            r = x % y\n",
    "        return y\n",
    "\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        total = \"0/1\"\n",
    "        cache = []\n",
    "        expression += '+'\n",
    "        for i in range(len(expression)):\n",
    "            if i != 0 and (expression[i] == '+' or expression[i] == '-'):\n",
    "                # compute sum + current value\n",
    "                cache_str = ''.join(cache)\n",
    "                cache_str_spl = cache_str.split('/')\n",
    "                numerator = cache_str_spl[0]\n",
    "                denominator = cache_str_spl[1]\n",
    "                total_split = total.split('/')\n",
    "                total_numerator = total_split[0]\n",
    "                total_denominator = total_split[1]\n",
    "                res_deno = float(denominator) * float(total_denominator)\n",
    "                res_nume = float(total_numerator) * float(denominator) + float(total_denominator) * float(numerator)\n",
    "                gcd = self.get_gcd(abs(res_deno), abs(res_nume))\n",
    "                if gcd == 0:\n",
    "                    total = \"0/1\"\n",
    "                else:\n",
    "                    res_deno /= gcd\n",
    "                    res_nume /= gcd\n",
    "                    total = f\"{int(res_nume)}/{int(res_deno)}\"\n",
    "                cache = []\n",
    "            cache.append(expression[i])\n",
    "        return total    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1  # 跳过除号\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        expression = expression.replace(\"-\", \"+-\")\n",
    "        list1 = expression.split(\"+\")\n",
    "        nums = []\n",
    "        for num in list1:\n",
    "            if num != \"\":\n",
    "                tmp = num.split(\"/\")\n",
    "                a, b = tmp[0], tmp[1]\n",
    "                nums.append([a,b])\n",
    "        result = nums[0]\n",
    "        if len(nums)==1:\n",
    "            return str(result[0]) + \"/\" + str(result[1])\n",
    "        else:\n",
    "            for i in range(1, len(nums)):\n",
    "                if result!=[]:\n",
    "                    a, b = int(nums[i][1])*int(result[0]) + int(nums[i][0])*int(result[1]), int(result[1])*int(nums[i][1])\n",
    "                    result = [a, b]\n",
    "            if a==0:\n",
    "                return str(result[0]) + \"/1\"\n",
    "            else:\n",
    "                print(f\"result = {result}\")\n",
    "                tmp = math.gcd(abs(a), abs(b))\n",
    "                return str(int(result[0]/tmp)) + \"/\" + str(int(result[1]/tmp))\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def fractionAddition(self, expression: str) -> str:\r\n",
    "\r\n",
    "        idx=0\r\n",
    "\r\n",
    "        L=len(expression)\r\n",
    "        x,y=0,1\r\n",
    "        sign=1\r\n",
    "\r\n",
    "        while idx<L:\r\n",
    "            if expression[idx]=='+' or expression[idx]=='-':           \r\n",
    "                sign=1 if expression[idx]=='+' else -1\r\n",
    "                idx+=1\r\n",
    "            else:\r\n",
    "                x1=0\r\n",
    "                while expression[idx].isnumeric():\r\n",
    "                    x1=x1*10+int(expression[idx])\r\n",
    "                    idx+=1\r\n",
    "                x1*=sign\r\n",
    "                idx+=1\r\n",
    "                y1=0\r\n",
    "                while idx<L and expression[idx].isnumeric():\r\n",
    "                    y1=y1*10+int(expression[idx])\r\n",
    "                    idx+=1\r\n",
    "                x=x*y1+x1*y\r\n",
    "                y*=y1\r\n",
    "\r\n",
    "        if x==0:\r\n",
    "            return '0/1'\r\n",
    "        g=math.gcd(abs(x),y)\r\n",
    "        return f'{x//g}/{y//g}'\r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x,y=0,1\n",
    "        i,n=0,len(expression)\n",
    "        while i<n:\n",
    "            #分子\n",
    "            x1,sign=0,1\n",
    "            if expression[i]=='-' or expression[i]=='+':\n",
    "                if expression[i]=='-':\n",
    "                    sign=-1\n",
    "                i+=1\n",
    "            while i<n and expression[i].isdigit():\n",
    "                x1=x1*10+int(expression[i])\n",
    "                i+=1\n",
    "            x1=sign*x1\n",
    "            i+=1\n",
    "\n",
    "            #分母\n",
    "            y1=0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1=y1*10+int(expression[i])\n",
    "                i+=1\n",
    "\n",
    "            x=x*y1+x1*y\n",
    "            y*=y1\n",
    "        if x==0:\n",
    "            return \"0/1\"\n",
    "        g=gcd(abs(x),y)\n",
    "        return f\"{x//g}/{y//g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1  # 分子，分母\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            # 读取分子\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "\n",
    "            # 读取分母\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x, y = 0, 1\n",
    "        i, n = 0, len(expression)\n",
    "        while i < n:\n",
    "            x1, sign = 0, 1\n",
    "            if expression[i] == '-' or expression[i] == '+':\n",
    "                if expression[i] == '-':\n",
    "                    sign = -1\n",
    "                i += 1\n",
    "            while i < n and expression[i].isdigit():\n",
    "                x1 = x1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x1 = sign * x1\n",
    "            i += 1\n",
    "            y1 = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y1 = y1 * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            x = x * y1 + x1 * y\n",
    "            y *= y1\n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x // g}/{y // g}\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from fractions import Fraction\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        d = 0\n",
    "        expression = expression.replace('-', '+-').split('+')\n",
    "        for i in expression:\n",
    "            if i != '':\n",
    "                d += Fraction(i)\n",
    "        return str(d) if str(d).find('/') != -1 else str(d) + '/1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        a, b = 0, 1 # a / b\n",
    "        i, n = 0, len(expression)\n",
    "        \n",
    "        while i < n:\n",
    "            num, sign = 0, 1\n",
    "            ch = expression[i]\n",
    "            if ch in ('-', '+'):\n",
    "                if ch == '-': sign = -1\n",
    "                i += 1\n",
    "            # 分子\n",
    "            while i < n and expression[i].isdigit():\n",
    "                num = num * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            \n",
    "            x = sign * num\n",
    "            \n",
    "            i += 1 # 跳过/号\n",
    "\n",
    "            # 分母\n",
    "            y = 0\n",
    "            while i < n and expression[i].isdigit():\n",
    "                y = y * 10 + int(expression[i])\n",
    "                i += 1\n",
    "            \n",
    "            a = a * y + x * b\n",
    "            b = b * y\n",
    "        \n",
    "        if a == 0: return '0/1'\n",
    "\n",
    "       \n",
    "        min_div = gcd(a, b)\n",
    "        \n",
    "        a //= min_div\n",
    "        b //= min_div\n",
    "\n",
    "        return \"{}/{}\".format(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        x,y = 0, 1\n",
    "        n = len(expression)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            # 分子\n",
    "            signal, x1 = 1, 0\n",
    "            if expression[i] in \"+-\":\n",
    "                if expression[i] == \"-\":\n",
    "                    signal = -1\n",
    "                i += 1\n",
    "\n",
    "            while expression[i].isdigit():\n",
    "                x1 = 10*x1 + int(expression[i])\n",
    "                i += 1\n",
    "\n",
    "            x1 *= signal\n",
    "\n",
    "            # \"/\"\n",
    "            i += 1  \n",
    "\n",
    "            # 分母\n",
    "            y1 = 0\n",
    "            while i<n and expression[i].isdigit():\n",
    "                y1 = 10*y1 + int(expression[i])\n",
    "                i += 1\n",
    "            \n",
    "            x,y = x * y1 + x1*y, y * y1 \n",
    "  \n",
    "        if x == 0:\n",
    "            return \"0/1\"\n",
    "\n",
    "        g = gcd(abs(x), y)\n",
    "        return f\"{x//g}/{y//g}\"\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "\n",
    "        def add(f1, f2):\n",
    "            num, den = f1[0]*f2[1] + f1[1]*f2[0], f1[1]*f2[1]\n",
    "            g = math.gcd(num, den)\n",
    "            return [num//g, den//g]\n",
    "        \n",
    "        ans = [0, 1]\n",
    "        i, n = 0, len(expression)\n",
    "        op = '+'\n",
    "        if expression[0] == '-':\n",
    "            op = '-'\n",
    "            i += 1\n",
    "\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j < n and expression[j] not in ('+', '-'):\n",
    "                j += 1\n",
    "            \n",
    "            f = list(map(int, expression[i:j].split('/')))\n",
    "            if op == '-':\n",
    "                f[0] = -f[0]\n",
    "            ans = add(ans, f)\n",
    "\n",
    "            if j == n:\n",
    "                break\n",
    "            op = expression[j]\n",
    "            i = j + 1\n",
    "\n",
    "        return '%d/%d' % (ans[0], ans[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            return gcd(b, a % b)\n",
    "\n",
    "\n",
    "        def lcm(a, b):\n",
    "            return abs(a * b) // gcd(a, b)\n",
    "\n",
    "\n",
    "        def list_lcm(lst):\n",
    "            lcm_result = lst[0]\n",
    "            for i in range(1, len(lst)):\n",
    "                lcm_result = lcm(lcm_result, lst[i])\n",
    "            return lcm_result\n",
    "        \n",
    "        target = expression.split('+')\n",
    "        numerator = []\n",
    "        denominator = []\n",
    "        for t in target:\n",
    "            t_start = 1 if t[0] != '-' else -1\n",
    "            ts = list(filter(lambda x: x != '', t.split('-')))\n",
    "            num_t = ts[0].split('/')\n",
    "            numerator.append(int(num_t[0]) * t_start)\n",
    "            denominator.append(int(num_t[1]))\n",
    "            for num in ts[1:]:\n",
    "                num_t = num.split('/')\n",
    "                numerator.append(int(num_t[0]) * -1)\n",
    "                denominator.append(int(num_t[1]))\n",
    "        common_multiple = list_lcm(denominator)\n",
    "        numerator_sum = int(sum(map(lambda x: x[0] * (common_multiple / x[1]), zip(numerator, denominator))))\n",
    "        common_divisor = gcd(numerator_sum, common_multiple)\n",
    "        return f'{int(numerator_sum / common_divisor)}/{int(common_multiple / common_divisor)}'\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def gcd(num1: int, num2: int) -> int:\n",
    "            if num1 % num2 == 0:\n",
    "                return num2\n",
    "            return gcd(num2, num1 % num2)\n",
    "\n",
    "        def add(num1: str, num2: str) -> str:\n",
    "            num1 = num1.split('/')\n",
    "            num2 = num2.split('/')\n",
    "            res_up = int(num1[0]) * int(num2[1]) + int(num2[0]) * int(num1[1])\n",
    "            res_down = int(num1[1]) * int(num2[1])\n",
    "            res_gcd = gcd(res_up, res_down)\n",
    "            return f'{res_up // res_gcd}/{res_down // res_gcd}'\n",
    "\n",
    "        ans = '0/1'\n",
    "        i, flag = (1, False) if expression[0] == '-' else (0, True)\n",
    "        num = ''\n",
    "        while i < len(expression):\n",
    "            if expression[i] not in '+-':\n",
    "                num += expression[i]\n",
    "            else:\n",
    "                if not flag:\n",
    "                    num = '-' + num\n",
    "                ans = add(ans, num)\n",
    "                num = ''\n",
    "                if expression[i] == '+':\n",
    "                    flag = True\n",
    "                else:\n",
    "                    flag = False\n",
    "            i += 1\n",
    "        if not flag:\n",
    "            num = '-' + num\n",
    "        ans = add(ans, num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fractionAddition(self, expression: str) -> str:\n",
    "        def gcd(a: int, b: int) -> int:\n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            if b == 0:\n",
    "                return a\n",
    "            c = a % b\n",
    "            return gcd(b, c)\n",
    "\n",
    "        nums = []\n",
    "        n = len(expression)\n",
    "        n1 = 0\n",
    "        n2 = 0\n",
    "        f = 1\n",
    "        s = expression + '+'\n",
    "        flag = True\n",
    "        for i in range(n + 1):\n",
    "            if s[i] == '-':\n",
    "                if n2 != 0:\n",
    "                    nums.append([f * n1, n2])\n",
    "                    n1 = 0\n",
    "                    n2 = 0\n",
    "                    flag = True\n",
    "                f = -1\n",
    "            elif s[i] == '+':\n",
    "                nums.append([f * n1, n2])\n",
    "                f = 1\n",
    "                n1 = 0\n",
    "                n2 = 0\n",
    "                flag = True\n",
    "            elif s[i] == '/':\n",
    "                flag = False\n",
    "            elif flag:\n",
    "                n1 = n1 * 10 + int(s[i])\n",
    "            else:\n",
    "                n2 = n2 * 10 + int(s[i])\n",
    "        if len(nums) == 1:\n",
    "            return expression\n",
    "        m = len(nums)\n",
    "        num = nums[0][1] * nums[1][1] // gcd(nums[0][1], nums[1][1])\n",
    "        for i in range(2, m):\n",
    "            num = num * nums[i][1] // gcd(num, nums[i][1])\n",
    "        # print(num)\n",
    "        son = 0\n",
    "        for i in range(m):\n",
    "            son += (nums[i][0] * (num // nums[i][1]))\n",
    "        ans = ''\n",
    "        if son < 0:\n",
    "            ans = '-'\n",
    "            son = -son\n",
    "        num1 = gcd(son, num)\n",
    "        son = son // num1\n",
    "        num = num // num1\n",
    "        ans += (str(son) + '/' + str(num))\n",
    "        return ans\n",
    "            \n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
